Gradient projeté

En optimisation mathématique, le gradient projeté est un vecteur dont la nullité exprime l'optimalité au premier ordre d'un problème d'optimisation avec contraintes convexes. Il est aussi utilisé dans la description et l'analyse de l'algorithme du gradient projeté.

De manière plus précise, le gradient projeté est la projection orthogonale du gradient en un point $x$ de la fonction que l'on cherche à minimiser, projection sur l'opposé du cône tangent au point $x$ à l'ensemble admissible du problème, supposé convexe.

Définition

Considérons le problème d'optimisation générique

$(P_{X})\qquad \inf _{x\in X}\;f(x),$

dans lequel on cherche à minimiser une fonction différentiable $f:\mathbb {E} \to \mathbb {R}$ sur une partie convexe $X$ d'un espace euclidien $\mathbb {E}$, dont le produit scalaire est noté $\langle \cdot ,\cdot \rangle$. Soit $x$ un point de $X$. On note

• $\nabla f(x)\in \mathbb {E}$ le gradient de $f$ en $x$,
• $T_{x}X$ le cône tangent à $X$ en $x$,
• $P_{C}$ le projecteur orthogonal sur un convexe fermé non vide $C$ de $\mathbb {E}$.

Alors le gradient projeté en $x$ est le vecteur $g^{\rm {\scriptscriptstyle P}}(x)\in \mathbb {E}$ défini par

$g^{\rm {\scriptscriptstyle P}}(x)=P_{-T_{x}X}\nabla f(x)=-P_{T_{x}X}(-\nabla f(x)).$

D'après la première expression, il s'agit de la projection orthogonale du gradient $\nabla f(x)$ sur $-T_{x}X$, qui est l'opposé du cône tangent à $X$ en $x$ (c'est un cône convexe fermé lorsque $X$ est convexe comme ici). D'après la seconde expression, on peut aussi dire que l'opposé du gradient projeté, $-g^{\rm {\scriptscriptstyle P}}(x)$, est la projection orthogonale de l'opposé du gradient, $-\nabla f(x)$, sur le cône tangent $T_{x}X$.

Propriétés

Expression de l'optimalité

Le gradient projeté peut être utilisé pour exprimer l'optimalité du problème $(P_{X})$ au premier ordre. On sait en effet que, si ${\bar {x}}\in X$ est solution du problème $(P_{X})$ et si $f$ est différentiable en ${\bar {x}}$, alors $\nabla f({\bar {x}})$ est dans le cône dual du cône tangent à $X$ en ${\bar {x}}$, ce qui veut dire que $\langle \nabla f({\bar {x}}),d\rangle \geqslant 0$, pour toute direction tangente $d\in T_{\bar {x}}X$. Cela s'écrit de manière compacte comme suit

$\nabla f({\bar {x}})\in (T_{\bar {x}}X)^{+}.$

On montre facilement que cette condition d'optimalité du premier ordre géométrique est équivalente à la nullité du gradient projeté :

$\nabla f({\bar {x}})\in (T_{\bar {x}}X)^{+}\qquad \Longleftrightarrow \qquad g^{\rm {\scriptscriptstyle P}}({\bar {x}})=0.$

Descente

S'il est non nul, l'opposé du gradient projeté est une direction de descente de $f$ en $x$, car on a

$\langle \nabla f(x),-g^{\rm {\scriptscriptstyle P}}(x)\rangle \leqslant -\|g^{\rm {\scriptscriptstyle P}}(x)\|^{2}.$

Projection du chemin de plus forte pente

Dans l'algorithme du gradient projeté, on examine depuis un itéré $x$, l'allure de la fonction $f$ à minimiser le long du chemin obtenu en projetant sur $X$ le chemin $\alpha \in \mathbb {R} _{+}\mapsto x-\alpha g$, où $g=\nabla f(x)$. Cette projection se confond avec le chemin $\alpha \in \mathbb {R} _{+}\mapsto x-\alpha g^{\rm {\scriptscriptstyle P}}$, où $g^{\rm {\scriptscriptstyle P}}\equiv g^{\rm {\scriptscriptstyle P}}(x)$, tant que $x-\alpha g^{\rm {\scriptscriptstyle P}}$ reste dans $X$. C'est ce qu'affirme le résultat suivant.

Projection du chemin de plus forte pente — Quel que soit $\alpha \geqslant 0$, on a

$P_{X}(x-\alpha g)=x-\alpha g^{\rm {\scriptscriptstyle P}}\qquad \Longleftrightarrow \qquad x-\alpha g^{\rm {\scriptscriptstyle P}}\in X.$

De plus, lorsque $X$ est polyédrique, ces propriétés ont lieu pour tout $\alpha >0$ petit.

Exemple

Le concept de gradient projeté s'utilise surtout lorsque la projection sur l'opposé du cône tangent est une opération aisée. C'est le cas si $X$ est le pavé

$[l,u]:=\{x\in \mathbb {R} ^{n}:l\leqslant x\leqslant u\},$

où les bornes $l\in {\bar {\mathbb {R} }}^{n}$et $u\in {\bar {\mathbb {R} }}^{n}$ peuvent prendre des valeurs infinies et vérifient $l<u$.

Soit $x\in [l,u]$. Alors, le cône tangent à $[l,u]$ en $x$ est donné par

$d\in T_{x}[l,u]\qquad \Longleftrightarrow \qquad \forall \,i\in [\![1,n]\!]:\quad d_{i}~\left\{{\begin{array}{lll}\geqslant 0&{\mbox{si}}&l_{i}=x_{i}\\\leqslant 0&{\mbox{si}}&\quad \ \ \ x_{i}=u_{i}.\end{array}}\right.$

Dès lors, si l'on munit $\mathbb {R} ^{n}$ du produit scalaire euclidien $(u,v)\in \mathbb {R} ^{n}\times \mathbb {R} ^{n}\mapsto \sum _{i=1}^{n}\,u_{i}v_{i}$, on a

$\forall \,i\in [\![1,n]\!]:\quad [g^{\rm {\scriptscriptstyle P}}(x)]_{i}=~\left\{{\begin{array}{lll}\textstyle \min(0,{\frac {\partial f}{\partial x_{i}}}(x))&{\mbox{si}}&l_{i}=x_{i}\\\textstyle {\frac {\partial f}{\partial x_{i}}}(x)&{\mbox{si}}&l_{i}<x_{i}<u_{i}\\\textstyle \max(0,{\frac {\partial f}{\partial x_{i}}}(x))&{\mbox{si}}&\quad \ \ \ x_{i}=u_{i}.\end{array}}\right.$

Donc, la condition d'optimalité du premier ordre $g^{\rm {\scriptscriptstyle P}}(x)=0$ s'écrit aussi

$\forall \,i\in [\![1,n]\!]:\quad {\frac {\partial f}{\partial x_{i}}}(x)~\left\{{\begin{array}{lll}\geqslant 0&{\mbox{si}}&l_{i}=x_{i}\\=0&{\mbox{si}}&l_{i}<x_{i}<u_{i}\\\leqslant 0&{\mbox{si}}&\quad \ \ \ x_{i}=u_{i}.\end{array}}\right.$

Annexe

Article connexe

• Gradient

Lien externe

• J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.

Bibliographie

• (en) P.H. Calamai, J.J. Moré (1987). Projected gradient methods for linearly constrained problems. Mathematical Programming, 39, 93-116. doi
• (en) J.J. Moré, G. Toraldo (1991). On the solution of large quadratic programming problems with bound constraints. SIAM Journal on Optimization, 1, 93–113. doi